package com.yq.leetcodeOld.tree;

/**
 * @ClassName Solution25
 * @Description TODO
 * @Author yaoqiang
 * @Date 2022/2/17 13:45
 * @Version 1.0
 */
public class Solution25 {
    public static void main(String[] args) {
        int[] input=new int[6];
        for (int i=1;i<input.length;i++){
            input[i]=i;
            System.out.println(input[i]);

        }
        //只能循环输出
        ListNode node1= new ListNode(input[1]);
        ListNode node2= new ListNode(input[2]);
        ListNode node3= new ListNode(input[3]);
        ListNode node4= new ListNode(input[4]);
        ListNode node5= new ListNode(input[5]);
        SingleLinkedList list=new SingleLinkedList();
        list.add(node1);
        list.add(node2);
        list.add(node3);
        list.add(node4);
        list.add(node5);
        System.out.println(list);
    }
    public ListNode reverseKgroup(ListNode head,int k){

//：head = [1,2,3,4,5], k = 2
//：[2,1,4,3,5]
        /**
         hair tail
        1、创建hair节点，让它和head相连，并创建一个pre
         2、用while循环head直到结束，意味着结束
            2.1将pre赋值给一个hair
            2.2用for循环截取k个，此刻tail就是k个结尾，里面注意判断如果小于k直接返回hair。next(表示处理完了，后续不需要处理了)
            2.3调用反转函数实现从head到tail的反转  reverse数组返回两个节点，反转的下一节点（开始就给临时节点了），反转后的头，分别赋值给head和hair
            2.4 将反转的和pre和nex想衔接
            2.5将tail给到pre，其实就是把pre移动到反转后的那个节点位置，下一个节点是k的下一组，将tail.next给到head,开启下一轮
         3、反转（head,tail）
                tail.next 给prev (此刻应该是空的) head备份一个给p
                while,当tail没到prev一直执行
                    head的next 给nex做为一个temp 开始交换：prev给p的next;p给prev;nex给p

         * */
        //
        ListNode hair = new ListNode(0);
        hair.next = head;
        ListNode pre = hair;
        //
        while (head != null) {
            //
            ListNode tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;
                if (tail == null) {
                    return hair.next;
                }
            }
            ListNode nex = tail.next;
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 把子链表重新接回原链表
            pre.next = head;
            tail.next = nex;
            pre = tail;
            head = tail.next;
        }

        return hair.next;
    }

    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode p = head;
        while (prev != tail) {
            ListNode nex = p.next;
            p.next = prev;
            prev = p;
            p = nex;
        }
        return new ListNode[]{tail, head};
    }

}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
